链式栈Stack——数据结构系列教程(c++版)

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

#endif // ENTITYS_H_INCLUDED
        

LinkedStack.h 头文件

#ifndef LINKEDSTACK_H_INCLUDED
#define LINKEDSTACK_H_INCLUDED

#include "Entitys.h"

//************************************************************************************************************************************************************************
//
//      类名：链表栈(LinkedStack)
//
//      概述：一个可复用的链表栈，存储结构采用链表实现，支持任意类型数据（模板泛型）。
//
//      说明：采用链表存储结构，栈的容量没限制，入栈出栈时间复杂度为O(1)
//
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//
//                                                                 栈节点结构体(StackNode)
//
//========================================================================================================================================================================
template <typename T>
struct StackNode
{
    T data;             //栈节点数据
    StackNode* next;    //下一个栈节点指针
};

//========================================================================================================================================================================
//
//                                                                链表栈结构体(LinkedStack)
//
//========================================================================================================================================================================
template <typename T>
struct LinkedStack{
    // ------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        StackNode<T> *top = nullptr;   // 栈顶指针

        //---------------声明私有成员函数---------------


    // ------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        LinkedStack() {
            top = nullptr;
        }

        int isEmpty();                  // 判断栈是否为空
        T getTop();                     // 获取栈顶元素（不弹出）
        void push(const T& value);     // 入栈
        T pop();                        // 出栈
        void deleteStack();             // 手动释放内存
        void print();                   // 打印栈数据（从栈底到栈顶，不修改top指针）

        // 析构函数：自动销毁栈，避免内存泄漏
        ~LinkedStack() {
            deleteStack();
        }
};

#endif // LINKEDSTACK_H_INCLUDED
                
                

LinkedStack.cpp 程序代码

#include <iostream>
#include"LinkedStack.h"

//---------------实现公共成员函数---------------

// 判断栈是否为空
template <typename T>
int LinkedStack<T>::isEmpty() {
    return top == nullptr;
}

// 获取栈顶元素（不弹出）
template <typename T>
T LinkedStack<T>::getTop() {
    if (isEmpty()) {
        return T();
    }
    return top->data;
}

//入栈
template <typename T>
void LinkedStack<T>::push(const T& value)
{
    StackNode<T> *p = new StackNode<T>;
    p->data = value;
    p->next = top;
    top = p;
}

//出栈
template <typename T>
T LinkedStack<T>::pop()
{
    T value;
    StackNode<T> *p = top;
    if(top != nullptr)
    {
        p = top;
        value = p->data;
        top = p->next;
        delete(p);
        return value;
    }
    else
    {
        printf("栈为空！\n");
        return T();
    }
}

// 释放内存
template <typename T>
void LinkedStack<T>::deleteStack() {
    while(top != nullptr)
    {
        StackNode<T> *p = top;
        top = p->next;
        delete(p);
    }
    top = nullptr;
}

// 打印栈数据（从栈底到栈顶，不修改top指针）
template <typename T>
void LinkedStack<T>::print() {
    if (isEmpty()) {
        printf("栈为空，无元素可打印！\n");
        return;
    }

    // 核心逻辑：链表栈仅能从栈顶遍历，需借助临时栈反转后打印（保证不修改原栈）
    LinkedStack tempStack; // 临时栈，用于反转元素
    StackNode<T>* curr = top;

    // 第一步：将原栈元素暂存到临时栈（原栈顶 → 临时栈底）
    while (curr != nullptr) {
        tempStack.push(curr->data);
        curr = curr->next;
    }

    // 第二步：遍历临时栈（从栈顶到栈底 = 原栈的栈底到栈顶）
    printf("栈元素（栈底 → 栈顶）：");
    curr = tempStack.top;
    while (curr != nullptr) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");

    // 可选：补充打印栈顶→栈底（直接遍历原栈即可）
    /*printf("栈元素（栈顶 → 栈底）：");
    curr = top;
    while (curr != nullptr) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");*/

    // 释放临时栈内存（避免泄漏）
    tempStack.deleteStack();
}             

// 显式实例化常用类型（避免链接错误，可选）
template class LinkedStack<int>;
template class LinkedStack<char>;
template class LinkedStack<float>;
template class LinkedStack<std::string>;
template class LinkedStack<Student>; // 新增：显式实例化Student类型
template class LinkedStack<PrintTask>; // 新增：显式实例化PrintTask类型
template class LinkedStack<Pos>; // 新增：显式实例化Pos类型

main.cpp 测试代码

#include "LinkedStack.h"
#include <iostream>
#include <string>

int main() {
    LinkedStack<int> stacks;

    // 1. 入栈测试
    printf("\n=== 入栈测试 ===\n");
    stacks.push(1);
    stacks.push(2);
    stacks.push(3);
    stacks.push(4);
    stacks.push(5);
    printf("入栈1、2、3、4、5后：\n");
    stacks.print();

    // 2. 出队测试
    printf("\n=== 出栈测试 ===\n");
    printf("出栈3次：");
    printf("%d ",stacks.pop());
    printf("%d ",stacks.pop());
    printf("%d \n",stacks.pop());
    printf("出栈后");
    stacks.print();
    
    return 0;
}

输出结果

=== 入栈测试 ===
入栈1、2、3、4、5后：
栈元素（栈底 → 栈顶）：1 2 3 4 5

=== 出栈测试 ===
出栈3次：5 4 3
出栈后栈元素（栈底 → 栈顶）：1 2
    

六、注意事项

七、应用场景

• 逆序处理的场景：进制转换、字符串逆序、数组逆序 → 栈天生做逆序；
• 匹配 / 成对校验的场景：括号匹配、标签匹配（HTML/XML）→ 左入栈，右出栈匹配；
• 回溯 / 反悔的场景：表达式求值、DFS 深度优先搜索、函数调用栈 → 走不通就回退（出栈）。

八、总结

• 栈是线性数据结构，核心特性是 LIFO（后进先出）；
• 核心操作是 Push（入栈）和 Pop（出栈），辅助操作是 getTop（查看栈顶）和 isEmpty（判断栈空）；
• 实现方式分为数组栈（简单高效，有容量限制）和链式栈（动态扩容，略复杂）；
• 核心应用包括括号匹配、DFS、函数调用栈、浏览器后退等，操作时间复杂度均为 O (1)。

本教程通过代码解析和实战示例，覆盖了栈的核心原理、关键操作实现和实际使用场景。栈作为基础数据结构，掌握栈的实现，是深入学习更复杂数据结构的重要基础。